package 二分查找;

/**
 * @author tmh
 * @date 2024/12/5 21:25
 * @description
 */
public class T33搜索旋转排序数组 {
    public int search(int[] nums, int target) {
        //先直接搜索旋转排序数组的最小值，然后判断target是在哪一侧
        int left = 0;
        int right = nums.length - 1;
        int n = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] > nums[n]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 旋转点所在的索引
        int rotationIndex = right;

        // Step 2: 判断 target 所在的区间
        left = 0;
        right = nums.length - 1;

        if (target >= nums[rotationIndex] && target <= nums[right]) {
            left = rotationIndex; // target 在右区间
        } else {
            right = rotationIndex - 1; // target 在左区间
        }

        // Step 3: 在确定的区间中进行二分查找
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 如果没有找到，返回 -1
        return -1;
    }
}
